1. Field of the Invention
The present invention relates generally to the field of cache memories and more specifically to a method and apparatus for updating status bits that depend on the MATCH signals in a multi-way set associative cache memory.
2. Prior Art
The least recently used (LRU) method is widely implemented in multi-way cache memory systems to maximize the cache hit rate. Under the LRU method, the cache memory system records in a LRU status array a limited history of how recently each cache data in the cache memory has been used. The LRU method selectively replaces the least recently used cache data when writing new data into the cache memory such that more recently used data is retained. Because more recently used cache data is more likely to be reused, the cache hit rate is increased.
For each address in the cache memory, the corresponding LRU array status bits indicate the way in which a match last occurred. For example, in a four-way set associative cache three LRU status bits are typically used to indicate the matching way as shown in Table 1.
TABLE 1 ______________________________________ LRU status bit scheme for a four-way cache ______________________________________ LRU0 A 1 value indicates a match in either way0 or way1; a 0 value indicates a match in either way2 or way3. LRU1 A 1 value indicates a match in way0; a 0 value indicates a match in way1. LRU2 A 1 value indicates a match in way2; a 0 value indicates a match in way3. ______________________________________
Typically, LRU status bits in the LRU array are updated during both cache read and write cycles. In a multi-way set associative cache memory, updating the LRU status bits during a read cycle is timing-critical since the new LRU status bit values depend on the MATCH signals originated in each way of the cache. On a read miss cycle, the old LRU status bit value in the array is preserved. Two ways to preserve the old LRU status bit are disabling any write to the data or reading the data and subsequently writing the same data back into the array. On a read hit cycle, the LRU status bit value is read, updated according to the values of the MATCH signals for each way, and then written into the LRU status bit array. The LRU array status bits are typically updated using combinational logic to directly implement the logic equations that define the updated LRU array status bits.
For example, the following are the logic equations for updating LRU status bits 0, 1, and 2 on a read cycle in a four-way set associative cache. EQU LRU0new=MATCH0 OR MATCH1 OR ((NOT MATCH2) AND (NOT MATCH3) AND LRU0old)EQ 1) EQU LRU1new=MATCH0 OR ((NOT MATCH0) AND (NOT MATCH1) AND LRU1old)(EQ 2) EQU LRU2new=MATCH2 OR ((NOT MATCH2) AND (NOT MATCH3) AND LRU2old)(EQ 3)
Typically these equations are implemented directly in circuitry utilizing a combination of AND, NAND, OR, NOR, or NOT logic gates. However, such a combinational logic circuit implementation is slow at providing the updated LRU status bit values.
Because the MATCH signals are valid very late in the read cycle of a cache, there is little time left to perform the required update of the LRU array status bit values before the write portion of the cycle begins. At higher clock speeds, direct combinational logic LRU status bit update circuitry does not meet the time constraints. Therefore, a method and apparatus for providing faster updating of the LRU array status bits during a read cycle of a cache memory is needed.
The constant drive for higher performance computer systems demands higher performance cache memory systems capable of running at higher clock speeds. Higher clock speeds allow less time for the timing-critical updating of cache memory status signals that depend on the cache MATCH signals. Therefore, a faster method for updating cache memory status bits that depend on the MATCH signals of a multi-way cache memory is needed.